#!/usr/bin/ruby
# -*- ruby -*-
#
# http://www.reddit.com/r/dailyprogrammer/comments/11shtj/10202012_challenge_105_intermediate_boolean_logic/

class Lexer
    def tokens(str)
        return str.split(//).select { |w| %w{0 1 T F t f | * ^ ! & ( )}.include?(w) }
    end
end

class Evaluator
    attr_reader :operands, :operators, :tokens

    def initialize(tokens)
        @operands  = []
        @operators = []
        @tokens = tokens
    end

    def eval
        @tokens.each do |token|
            if operand?(token)
                handle_operand(token)
            elsif operator?(token)
                handle_operator(token)
            elsif grouping?(token)
                handle_grouping(token)
            else
                raise "Unknown token #{token}"
            end
        end

        until @operands.size == 1
            process_operator(@operators.pop)
        end

        return @operands.first
    end

    def operand?(token)
        %w{0 1 T F t f}.include?(token)
    end

    def operator?(token)
        %w{| * ^ ! &}.include?(token)
    end

    def grouping?(token)
        %w{( )}.include?(token)
    end

    def normalize(operator)
        return true  if %w{1 T t}.include?(operator)
        return false if %w{0 F f}.include?(operator)
        raise "Unknown operator #{operator}"
    end

    def handle_operand(token)
        @operands << normalize(token)
    end

    def handle_operator(token)
        while precedence_higher?(@operators.last, token)
            operator = @operators.pop

            process_operator(operator)
        end

        @operators << token
    end

    def process_operator(operator)
        # Pop off the top operator and process it and put it back on the operand stack
        @operands << process(operator, @operands.pop(ary(operator)))
    end

    def precedence_higher?(operator_1, operator_2)
        # ! has the highest precedence
        # | * ^ & have equal prededence
        return operator_1 == '!'
    end

    def process(operator, operands)
        if operator == '!'
            return ! operands[0]
        elsif operator == '^'
            return operands[0] ^ operands[1]
        elsif operator == '*' || operator == '&'
            return operands[0] && operands[1]
        elsif operator == '|'
            return operands[0] || operands[1]
        end
    end

    def ary(operator)
        return 1 if operator == '!'
        return 2
    end

    def handle_grouping(token)
        if '(' == token
            @operators << token
        elsif ')' == token
            until @operators.last == '('
                process_operator(@operators.pop)
            end

            @operators.pop
        end
    end
end

ARGV.each do |expr|
    tokens = Lexer.new.tokens(expr)

    puts "'#{expr}' => #{Evaluator.new(tokens).eval}"
end
